#ifndef GAMEENGINE_CORE_GRAPH_QUADTREE_HPP
#define GAMEENGINE_CORE_GRAPH_QUADTREE_HPP

#ifdef GAMEENGINE_NAMESPACES
namespace GameEngine {
#endif


//=====================================================================


//! Default constructor
/*!
 @param max_depth The maximum depth allowed for the quadtree structure
 */
template <class E, class T>
Quadtree<E,T>::Quadtree(int max_depth) {
	subdivide(node_, max_depth);
}

//! Constructor
/*!
 @param box The box associated to the whole quadtree
 @param max_depth The maximum depth allowed for the quadtree structure
 */
template <class E, class T>
Quadtree<E,T>::Quadtree(const Box2d<T>& box, int max_depth) : node_(box) {
	subdivide(node_, max_depth);
}

//! Copy constructor
/*!
 @param rhs The quadtree to copy
 */
template <class E, class T>
Quadtree<E,T>::Quadtree(const Quadtree& rhs) : node_(rhs.node_), elements_(rhs.elements_) {}

//! Destructor
template <class E, class T>
Quadtree<E,T>::~Quadtree() {}

//! Assignment operator
/*!
 @param rhs The quadtree to copy
 */
template <class E, class T>
Quadtree<E,T>& Quadtree<E,T>::operator=(const Quadtree& rhs) {
	if ( &rhs != this ) {
		node_ = rhs.node_;
		elements_ = rhs.elements_;
	}
	return *this;
}

//! Accessor to the elements of the quadtree (read only)
/*!
 @return A constant reference to the elements of the quadtree
 */
template <class E, class T>
const std::vector<E>& Quadtree<E,T>::elements() const {
	return elements_;
}

//! Accessor to the elements of the quadtree (read-write)
/*!
 @return A reference to the elements of the quadtree
 */
template <class E, class T>
std::vector<E>& Quadtree<E,T>::elements() {
	return elements_;
}

//! Try to add the element to the quadtree
/*!
 @param element The element to add
 @param location The location associated to the element
 @param unique If set to true, forbids the element to be added multiple times to the quadtree
 @return True if the element could be added to this quadtree, false otherwise. An element may
         not be added if its location does not fit with the box of the main quadtree node.
 */
template <class E, class T>
bool Quadtree<E,T>::add_element(const E& element, const Point2d<T>& location, bool unique) {
	// Check the location
	if ( node_.box().inside(location) == false ) return false;

	// Check uniqueness
	if ( unique == true ) {
		if ( find_element(element) == true ) return false;
	}

	// Add the element
	elements_.push_back(element);
	node_.add_element((QuadtreeIndex)((int)elements_.size()-1), location, false);
	return true;
}

//! Try to add the element to the quadtree
/*!
 @param element The element to add
 @param location The location associated to the element
 @param unique If set to true, forbids the element to be added multiple times to the quadtree
 @return True if the element could be added to this quadtree, false otherwise. An element may
         not be added if its location does not fit with the box of the main quadtree node.
 */
template <class E, class T>
bool Quadtree<E,T>::add_element(const E& element, const Box2d<T>& location, bool unique) {
	// Check the location
	if ( node_.box().overlap(location) == false ) return false;

	// Check uniqueness
	if ( unique == true ) {
		if ( find_element(element) == true ) return false;
	}

	// Add the element
	elements_.push_back(element);
	node_.add_element((QuadtreeIndex)((int)elements_.size()-1), location);
	return true;
}

//! Try to remove the element from this quadtree
/*!
 @param element The element to remove
 @return The number of elements that were removed from the quadtree
 @note This function is quite slow and should be called as little as possible. Future versions
       of GameEngine are expected to increase the speed of this function.
 */
template <class E, class T>
typename Quadtree<E,T>::ElementCount Quadtree<E,T>::remove_element(const E& element) {
	ElementCount res = 0;

	// Look for the elements of this quadtree node
	QuadtreeIndex index = 0;
	int count = (int)elements_.size(), cur_count = 0;
	for ( std::vector<E>::iterator it = elements_.begin(); it != elements_.end(); ++it ) {
		++cur_count;
		// Iterate over the elements of the quadtree
		if ( *it == element ) {
			// Remove the associated index in the quadtree node of the quadtree
			// Iterate over the non-empty nodes of the quadtree
			for ( Node::Iterator itr(node_, QuadtreeNodeItr::NonEmptyNodes); itr.more(); itr.next() ) {
				// Iterate over the elements of this quadtree node
				std::vector<QuadtreeIndex>& elements = itr.cur().elements();
				int count2 = (int)elements.size(), cur_count2 = 0;
				for ( std::vector<QuadtreeIndex>::iterator ite = elements.begin(); ite != itr.cur().elements().end(); ++ite ) {
					++cur_count2;

					// Nothing to do if index is below index to remove
					if ( *ite < index ) continue;

					// If this is the index to remove, remove it
					if ( *ite == index ) {
						elements.erase(ite);
						if ( cur_count2 == count2 ) break;
						continue;
					}

					// If index is greater than the index to remove, decrease it
					--(*ite);
				}
			}

			// Remove the element from the quadtree
			elements_.erase(it);
			++res;
			if ( cur_count == count ) break;
		}
		++index;
	}

	// Return the result
	return res;
}

//! Try to find the element in this quadtree
/*!
 @param element The element to find
 @return True if element could be found, false otherwise
 */
template <class E, class T>
bool Quadtree<E,T>::find_element(const E& element) const {
	// Look for the elements of this quadtree node
	for ( std::vector<E>::const_iterator it = elements_.begin(); it != elements_.end(); ++it ) {
		if ( *it != element ) continue;
		return true;
	}

	// Return the result
	return false;
}

//! Try to simplify the quadtree by removing all nodes whose number of elements is below given number
/*!
 @param nb_elements The threshold for the number of elements to keep the quadtree node
 */
template <class E, class T>
bool Quadtree<E,T>::simplify(ElementCount nb_elements) {
	return simplify(node_, nb_elements);
}

//! Try to simplify the quadtree node by removing all children nodes whose number of elements is below given number
/*!
 @param node The quadtree node to simplify
 @param nb_elements The threshold for the number of elements to keep the quadtree node
 */
template <class E, class T>
bool Quadtree<E,T>::simplify(Node& node, ElementCount nb_elements) {
	// Check if node can be simplified
	Node* children = node.children();
	if ( children == nil ) return true;

	// Check the number of elements
	if ( node.nb_elements() < nb_elements ) {
		node.merge(false);
		return true;
	}

	// Recursively test the children
	bool res = true;
	for ( int k = 0; k < 4; ++k ) {
		res &= simplify(children[k], nb_elements);
	}
	return res;
}

//! Recursively subdivide the quadtree node until given recursion level has been reached
/*!
 @param node The node to subdivide
 @param level The depth of the quadtree below this node
 @return True if node could be subdivided at the recursion level, false otherwise
 */
template <class E, class T>
bool Quadtree<E,T>::subdivide(Node& node, int level) {
	// Finished the recursion
	if ( level <= 0 ) return true;

	// Subdivide the node
	if ( node.subdivide() == false ) return false;

	// Subdivide the descendants
	Node* children = node.children();
	bool res = true;
	for ( int k = 0; k < 4; ++k ) {
		res &= subdivide(children[k],level-1);
	}

	// Return the result
	return res;
}

//! Get the low-level quadtree node that covers the given location
/*!
 @param location The location that should be queried
 @return A pointer to the low-level quadtree node that covers the given location (may
         be nil if the location does not fit the box of this node)
 */
template <class E, class T>
typename const Quadtree<E,T>::Node* Quadtree<E,T>::get_node(const Point2d<T>& location) const {
	return node_.get_node(location);
}

//! Get the low-level quadtree node that covers the given location
/*!
 @param location The location that should be queried
 @return A pointer to the low-level quadtree node that covers the given location (may
         be nil if the location does not fit the box of this node)
 */
template <class E, class T>
typename Quadtree<E,T>::Node* Quadtree<E,T>::get_node(const Point2d<T>& location) {
	return node_.get_node(location);
}

//! Get the quadtree nodes that cover the given location
/*!
 @param location The location that should be queried
 @param type The type of nodes to be considered
 @return A pointer to the low-level quadtree node that covers the given location (may
         be nil if the location does not fit the box of this node)
 */
template <class E, class T>
std::list< typename const Quadtree<E,T>::Node* > Quadtree<E,T>::get_nodes(const Box2d<T>& location, QuadtreeNodeItr::QuadtreeNodeItrType type) const {
	return node_.get_nodes(location, type);
}

//! Get the quadtree nodes that cover the given location
/*!
 @param location The location that should be queried
 @param type The type of nodes to be considered
 @return A pointer to the low-level quadtree node that covers the given location (may
         be nil if the location does not fit the box of this node)
 */
template <class E, class T>
std::list< typename Quadtree<E,T>::Node* > Quadtree<E,T>::get_nodes(const Box2d<T>& location, QuadtreeNodeItr::QuadtreeNodeItrType type) {
	return node_.get_nodes(location, type);
}


//=====================================================================


#ifdef GAMEENGINE_NAMESPACES
} // namespace GameEngine
#endif

#endif
